#include "mySearch.h"
#include <iostream>
#include <string>
#include<stack>

using namespace std;

SSTable::SSTable()
{
    this->length=0;
}

SSTable::SSTable(int length,int* ori)
{
    this->length=length;
    origin=new int[length];
    for(int i=0;i<length;i++)
    {
        origin[i]=ori[i];
    }
}

SSTable::~SSTable()
{
    delete [] origin;
}

int SSTable::getLength()
{
    return length;
}

int* SSTable::getOrigin()
{
    return origin;
}

void SSTable::setLength(int length)
{
    this->length=length;
}

void SSTable::setOrigin(int* origin)
{
    this->origin=origin;
}

void SSTable::binsearch_circle(int start, int end, int target, int &result)
{
    int middle=(start+end)/2;
    if(target==origin[middle])
    {
        result=middle;
        return;
    }
    else if(target>origin[middle])
    {
        if(middle+1==end)
        {
            return;
        }
        binsearch_circle(middle,end,target,result);
    }
    else if(target<origin[middle])
    {
        if(start+1==middle)
        {
            return;
        }
        binsearch_circle(start,middle,target,result);
    }
}

int SSTable::binSearch(int val)
{
    int result=-1;

    if(val==origin[0])
    {
        return 0;
    }
    else if(val==origin[length])
    {
        return length;
    }
    else
    {
        binsearch_circle(0,length,val,result);
    }
    return result;
}

BSTreeNode::BSTreeNode()
{
    lchild=NULL;
    rchild=NULL;
}

BSTreeNode::BSTreeNode(int d)
{
    data=d;
    lchild=NULL;
    rchild=NULL;
}

BSTreeNode::BSTreeNode(int d, BSTreeNode* l, BSTreeNode* r)
{
    data=d;
    lchild=l;
    rchild=r;
}

BSTreeNode::~BSTreeNode()
{

}

int BSTreeNode::getData()
{
    return data;
}

BSTreeNode* BSTreeNode::getLChild()
{
    return lchild;
}

BSTreeNode* BSTreeNode::getRChild()
{
    return rchild;
}

void BSTreeNode::setData(int data)
{

}

void BSTreeNode::setLChild(BSTreeNode* lchild)
{

}

void BSTreeNode::setRChild(BSTreeNode* rchild)
{

}

BSTree::BSTree()
{
    num=0;
    root=new BSTreeNode;
}

BSTree::BSTree(int n, int* data)
{
    num=n;
    root=new BSTreeNode(data[0]);
    for(int i=1;i<num;i++)
    {
        BSTreeNode* curNode=root;
        while(1)
        {
            if(data[i]>curNode->data)
            {
                if(curNode->rchild==NULL)
                {
                    curNode->rchild=new BSTreeNode(data[i]);
                    break;
                }
                else
                {
                    curNode=curNode->rchild;
                }
            }
            else if(data[i]<curNode->data)
            {
                if(curNode->lchild==NULL)
                {
                    curNode->lchild=new BSTreeNode(data[i]);
                    break;
                }
                else
                {
                    curNode=curNode->lchild;
                }
            }
            else
            {
                break;
            }
        }
    }
}
void BSTree::deleteTree(BSTreeNode *p)
{
        if (p == NULL)//判断是不是结点是否为空
        {
            return;
        }
        if (p->lchild)//判断结点是不是有左子树
            deleteTree(p->lchild);//递归调用，销毁左子树，下面同理
        if (p->rchild)
            deleteTree(p->rchild);
        delete p;
        p = NULL;
}
BSTree::~BSTree()
{
    deleteTree(root);
}

int BSTree::getNum()
{

}

BSTreeNode* BSTree::getRoot()
{

}

void BSTree::setNum(int num)
{

}

void BSTree::setRoot(BSTreeNode* root)
{

}

void BSTree::printTemp(BSTreeNode* root, string& result)
{
    if(root==NULL)
    {
        return;
    }
    string a=to_string(root->data);
    result=result+a;
    result=result+" ";
    printTemp(root->lchild,result);//递归遍历左子树
    printTemp(root->rchild,result);//递归遍历右子树
}

string BSTree::printTree()
{
    string result="";
    printTemp(root,result);
    return result;
}

bool BSTree::searchNode(int val){
    BSTreeNode* curNode=root;
    while(1)
    {
        if(curNode==NULL)
        {
            return false;
        }
        if(val==curNode->data)
        {
            return true;
        }
        else if(val>curNode->data)
        {
            curNode=curNode->rchild;
        }
        else
        {
            curNode=curNode->lchild;
        }
    }
}

bool BSTree::searchNode(int val, BSTreeNode *&targetNode, BSTreeNode *&frontNode, int &direction)
{
    BSTreeNode* curNode=root;
    BSTreeNode* tempNode=curNode;
    int dir;
    while(1)
    {
        if(curNode==NULL)
        {
            return false;
        }
        if(val==curNode->data)
        {
            targetNode=curNode;
            frontNode=tempNode;
            direction=dir;
            return true;
        }
        else if(val>curNode->data)
        {
            dir=1;
            tempNode=curNode;
            curNode=curNode->rchild;
        }
        else
        {
            dir=0;
            tempNode=curNode;
            curNode=curNode->lchild;
        }
    }
}

bool BSTree::addNode(int val)
{
    BSTreeNode* curNode=root;
    BSTreeNode* frontNode=curNode;
    int direction;
    while(1)
    {
        if(curNode==NULL)
        {
            if(direction)
            {
                frontNode->rchild=new BSTreeNode(val);
            }
            else
            {
                frontNode->lchild=new BSTreeNode(val);
            }
            return true;
        }
        if(val==curNode->data)
        {
            return false;
        }
        else if(val>curNode->data)
        {
            direction=1;
            frontNode=curNode;
            curNode=curNode->rchild;
        }
        else
        {
            direction=0;
            frontNode=curNode;
            curNode=curNode->lchild;
        }
    }
}

BSTreeNode *BSTree::left_right(BSTreeNode *tree)
{
    BSTreeNode* curNode=tree;
    BSTreeNode* frontNode=curNode;
    while(1)
    {
        if(curNode==NULL)
        {
            return frontNode;
        }
        else
        {
            frontNode=curNode;
            curNode=curNode->rchild;
        }
    }
}

void BSTree::deleteX(int x)
{
    stack<BSTreeNode*> nodeList;
    BSTreeNode* curNode=root;
    int n=0;
    while(n<num)
    {
        if(curNode->lchild!=NULL)
        {
            nodeList.push(curNode);
            curNode=curNode->lchild;
        }
        else
        {
            if(curNode->rchild!=NULL)
            {
                nodeList.push(curNode);
                curNode=curNode->rchild;
            }
            else
            {
                if(curNode->data<=x)
                {
                    deleteNode(curNode->data);
                }
                curNode=nodeList.top();
                nodeList.pop();
            }
        }
        n++;
    }
}

bool BSTree::deleteNode(int val)
{
    int direction;
    BSTreeNode *targetNode;
    BSTreeNode *frontNode;
    if(searchNode(val,targetNode,frontNode,direction))
    {
        if(targetNode->lchild==NULL&&targetNode->rchild==NULL)
        {
            delete targetNode;
            if(direction)
            {
                frontNode->rchild=NULL;
            }
            else
            {
                frontNode->lchild=NULL;
            }
        }
        else if(targetNode->lchild!=NULL&&targetNode->rchild==NULL)
        {
            if(direction)
            {
                frontNode->rchild=targetNode->lchild;
            }
            else
            {
                frontNode->lchild=targetNode->lchild;
            }
            delete targetNode;
        }
        else if(targetNode->lchild==NULL&&targetNode->rchild!=NULL)
        {
            if(direction)
            {
                frontNode->rchild=targetNode->rchild;
            }
            else
            {
                frontNode->lchild=targetNode->rchild;
            }
        }
        else
        {
            BSTreeNode* temp=left_right(targetNode->lchild);
            int a=temp->data;
            bool b=deleteNode(temp->data);
            targetNode->data=a;
        }
        return true;
    } 
    else
    {
        return false;
    }  
}